home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / man / oldman3 / Binary_Tree.3T < prev    next >
Text File  |  1992-06-29  |  7KB  |  226 lines
  1. .TH BINARY_TREE
  2. .SH NAME
  3. Binary_Tree<Type>\f1  A parameterized binary tree class
  4. .SH SYNOPSIS
  5. #include <cool/Binary_Tree.h>
  6. .SH DESCRIPTION
  7. The \f3Binary_Tree<Type>\f1 class implements simple, dynamic, sorted  sequences. 
  8. Users requiring a data structure for unsorted sequences whose structure and 
  9. organization is more under the control of the programmer are referred to the 
  10.  N_Tree 
  11. class. The \f3Binary_Tree<Type>\f1 class is derived from 
  12.  Binary_Tree 
  13. and is a 
  14. friend of the 
  15.  Binary_Node< Type >
  16. class, also parameterized over the same 
  17.  Type . 
  18. There is no attempt made to balance or prune the tree. Nodes are added to a 
  19. particular subtree at the direction of the collating function. For example, a 
  20. lopsided tree results if a tree is parameterized for integers and the tree uses 
  21. the default integer comparison operators whose elements are added in increasing 
  22. order. Likewise, a lopsided tree results after many items have been added and 
  23. removed.
  24. .PP
  25. The 
  26.  Binary_Tree< Type > 
  27. class implements the notion of a current position. This 
  28. is useful for iterating through the nodes of a tree. The current position is 
  29. maintained in a data member of type 
  30.  Binary_Tree_state 
  31. and is set or reset by 
  32. all member functions affecting elements in the class. Member functions are 
  33. provided to reset the current position, move to the next and previous elements, 
  34. find an element, and get the value at the current position. The 
  35.  Iterator< Type > 
  36. class provides a mechanism to save and restore the state associated with the 
  37. current position, thus allowing the programmer to use multiple iterators over 
  38. the same instance of a tree.
  39. .SH Base Classes
  40.  Binary_Tree, 
  41. .SH Friend Classes
  42. None
  43. .SH Public Constructors    
  44. .TP
  45.  Binary_Tree<Type> ();
  46. Allocates a binary tree object with the root pointer set to 
  47.  
  48.  NULL .
  49. .TP
  50. \f3Binary_Tree<Type> (const Binary_Tree<Type>& bt\f3);\f1
  51. Duplicates the structure of another binary tree object
  52.  bt .
  53. .SH Member Functions
  54. .TP
  55.  void balance ();
  56. Builds a perfectly balanced binary tree from the existing tree structure and 
  57. deletes the old tree and storage.
  58. .TP
  59.  void clear ();
  60. Empties the tree and deallocates all memory for nodes and internal structures.
  61. .TP
  62.  inline long count () const;
  63. Returns the number of nodes in the tree structure.
  64. .TP
  65.  inline Binary_Tree_state& current_position ();
  66. Returns a reference to the state information associated with the current 
  67. position. This function should be used with the \f3Iterator<Type>\f1 class to save 
  68. and restore the current position, thus facilitating multiple iterators over an 
  69. instance of binary tree.
  70. .TP
  71. \f3Boolean find (const Type& value\f3);\f1
  72. Searches for 
  73.  value 
  74. in the tree structure. If found, this function updates the 
  75. current position and returns 
  76.  
  77.  TRUE ; 
  78. otherwise, this function invalidates the 
  79. current position and returns 
  80.  
  81.  FALSE .
  82. .TP
  83. \f3Binary_Node<Type>* \f3get_root () const;\f1
  84. Returns a pointer to the root node of the tree.
  85. .TP
  86.  Boolean next ();
  87. Advances the current position to the next element in the tree and returns 
  88.  
  89.  TRUE . 
  90. If the current position is invalid, this function sets the current position to 
  91. the first element and returns 
  92.  
  93.  TRUE . 
  94. If the current position is the last 
  95. element in the tree, this function invalidates the current position and returns 
  96.  
  97.  FALSE .  
  98. .TP
  99. \f3Binary_Node<Type>* \f3node ();\f1
  100. Returns a pointer to the current node object.
  101. .TP
  102. \f3Binary_Tree<Type>& \f3operator= (Binary_Tree<Type>& bt\f3);\f1
  103. Overloads the assignment operator to duplicate another binary tree object 
  104.  bt 
  105. by copying all nodes and value to the binary tree object. This function returns a 
  106. reference to the updated binary tree object.
  107. .TP
  108. \f3inline Boolean operator== (const Binary_Tree<Type>& bt\f3) const;\f1
  109. Overloads the equality operator for the \f3Binary_Tree<Type>\f1 class. This function 
  110. returns 
  111.  
  112.  TRUE 
  113. if \f2bt\f1 is equal to the binary tree object; otherwise, this function 
  114. returns 
  115.  
  116.  FALSE .
  117. .TP
  118. \f3inline Boolean operator!= (const Binary_Tree<Type>& bt\f3) const;\f1
  119. Overloads the inequality operator for the \f3Binary_Tree<Type>\f1 class. This function returns 
  120.  
  121.  TRUE 
  122. if 
  123.  bt 
  124. is unequal to the binary tree object; otherwise, 
  125. this function returns
  126.  
  127.  FALSE .
  128. .TP
  129.  Boolean prev ();
  130. Moves the current position to the previous element in the tree and returns
  131.  
  132.  TRUE . 
  133. If the current position is invalid, this function sets the current 
  134. position to the last element and returns 
  135.  
  136.  TRUE , 
  137. thus facilitating reverse traversal through the tree.  If the current position is the first element in the tree, this function invalidates the current position and returns
  138.  
  139.  FALSE .
  140. .TP
  141. \f3inline Boolean put (const Type& value\f3);\f1
  142. Adds
  143.  value 
  144. to the tree structure if not already present. This function returns 
  145.  
  146.  TRUE 
  147. if the item is added; otherwise, this function  returns 
  148.  
  149.  FALSE . 
  150. This 
  151. function invalidates the current position.
  152. .TP
  153.  inline Boolean remove ();
  154. Removes the node at the current position from the tree structure and returns 
  155.  
  156.  TRUE . 
  157. This function invalidates the current position of the binary tree object. 
  158. If the current position is out of range, an 
  159.  \f3\f3Error\f1\f1 
  160. exception is raised and this 
  161. function returns 
  162.  
  163.  FALSE .
  164. .TP
  165. \f3inline Boolean remove (const Type& value\f3);\f1
  166. Removes 
  167.  value 
  168. from the tree structure if present. This function returns 
  169.  
  170.  TRUE 
  171. if 
  172. the specified argument is successfully removed; otherwise, this function 
  173. returns
  174.  
  175.  FALSE . 
  176. This function invalidates the current position.
  177. .TP
  178.  inline void reset ();
  179. Invalidates the current position of the binary tree object.
  180. .TP
  181. \f3void set_compare (\f2Binary_Tree_Compare \f3= NULL);\f1
  182. Sets the comparison function that is to be used in all logical comparison 
  183. tests. 
  184.  Binary_Tree_Compare 
  185. is a function of type 
  186.  Boolean 
  187. (\f2*Function\f1)(\f3const Type&\f1, \f3const Type&\f1).  If no argument is provided, the 
  188.  operator==
  189. for the type 
  190. over which the class is parameterized is used.
  191. .TP
  192.  inline long tree_depth ();
  193. Returns the zero-relative depth of the tree structure. 
  194.  
  195. .TP
  196.  Type& value ();
  197. Returns a reference to the node value at the current position. If the current 
  198. position is invalid, an 
  199.  \f3\f3Error\f1\f1 
  200. exception is raised.
  201. .SH Friend Functions
  202. .TP
  203. \f3friend ostream& operator<< (ostream& \f2os\f3, const Binary_Tree<Type>& bt\f3);\f1
  204. Accepts a binary tree reference and outputs the structure by printing it 
  205. sideways, where the root is printed at the left margin. To obtain the standard 
  206. orientation, rotate the output 90 degrees clockwise. This function returns a 
  207. reference to the output stream.
  208. .TP
  209. \f3friend ostream& operator<< (ostream& \f2os\f3, const Binary_Tree<Type>* bt\f3);\f1
  210. Accepts a binary tree pointer and outputs the structure by printing it 
  211. sideways, where the root is printed at the left margin. To obtain the standard 
  212. orientation, rotate the output 90 degrees clockwise. This function returns a 
  213. reference to the output stream.
  214. .SH COPYRIGHT
  215.  
  216. Copyright (C) 1991 Texas Instruments Incorporated.
  217.  
  218. Permission is granted to any individual or institution to use, copy, modify,
  219. and distribute this software, provided that this complete copyright and
  220. permission notice is maintained, intact, in all copies and supporting
  221. documentation.
  222.  
  223. Texas Instruments Incorporated provides this software "as is" without
  224. express or implied warranty.
  225.  
  226.